//
//  Problem1200.swift
//  LeetCode
//
//  Created by 武侠 on 2023/6/25.
//  Copyright © 2023 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 1200. 最小绝对差    简单

 给你个整数数组 arr，其中每个元素都 不相同。
 请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。
 每对元素对 [a,b] 如下：
    a , b 均为数组 arr 中的元素
    a < b
    b - a 等于 arr 中任意两个元素的最小绝对差
 示例 1：
     输入：arr = [4,2,1,3]
     输出：[[1,2],[2,3],[3,4]]
 示例 2：
     输入：arr = [1,3,6,10,15]
     输出：[[1,3]]
 示例 3：
     输入：arr = [3,8,-10,23,19,-4,-14,27]
     输出：[[-14,-10],[19,23],[23,27]]
 提示：
     2 <= arr.length <= 10^5
     -10^6 <= arr[i] <= 10^6
 */
class Problem1200: NSObject {
    /*
     思路：先计算在排序  超时
     设：minValue 为最小的绝对差，result为存储最小绝对差的数组
     1: 遍历数组arr，计算出数组中每2个值的绝对差 b - a
     2: 只要 b-a < minValue，就更新minValue=b-a; reuslt=[b,a]
     3: 升序排序result
     */
    func minimumAbsDifference(_ arr: [Int]) -> [[Int]] {
        var minValue = Int.max
        var result:[[Int]] = []
        
        var temp = 0
        for i in (0..<arr.count-1) {
            for j in (i+1..<arr.count) {
                temp = abs(arr[i] - arr[j])
                if temp < minValue {
                    minValue = temp
                    if arr[i] > arr[j] {
                        result = [[arr[j], arr[i]]]
                    } else {
                        result = [[arr[i], arr[j]]]
                    }
                } else if temp == minValue {
                    if arr[i] > arr[j] {
                        result.append([arr[j], arr[i]])
                    } else {
                        result.append([arr[i], arr[j]])
                    }
                }
            }
        }
        
        return result.sorted { n1, n2 in
            return n1[0] < n2[0]
        }
    }
    
    /*
     思路：先排序在计算 ✅
     设：minValue 为最小的绝对差，result为存储最小绝对差的数组
     1: 遍历数组arr，计算出数组中每2个值的绝对差 b - a
     2: 只要 b-a < minValue，就更新minValue=b-a; reuslt=[b,a]
     3: 升序排序result
     */
    func minimumAbsDifference2(_ arr: [Int]) -> [[Int]] {
        var minValue = Int.max
        var result:[[Int]] = []
        
        let list = arr.sorted()
        for i in (0..<list.count-1) {
            if list[i+1] - list[i] < minValue {
                result = [[list[i], list[i+1]]]
                minValue = list[i+1] - list[i]
            } else if list[i+1] - list[i] == minValue {
                result.append([list[i], list[i+1]])
            }
        }
        
        return result
    }
}
